//编写一个函数来查找字符串数组中的最长公共前缀。 
//
// 如果不存在公共前缀，返回空字符串 ""。 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["flower","flow","flight"]
//输出："fl"
// 
//
// 示例 2： 
//
// 
//输入：strs = ["dog","racecar","car"]
//输出：""
//解释：输入不存在公共前缀。 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 200 
// 0 <= strs[i].length <= 200 
// strs[i] 仅由小写英文字母组成 
// 
//
// Related Topics 字典树 字符串 👍 2989 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-11-13 19:51:58
 * @description 14.最长公共前缀
 */
public class LongestCommonPrefix{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new LongestCommonPrefix().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*横向、纵向扫描
		 * 横向：比较临近的，更新最长公共前缀，没遍历完就是空时，就不继续了
		 * 纵向：依次遍历每个字符串的每个位置上的字符，相等就继续，不同就停止*/
    public String longestCommonPrefix4(String[] strs) {
		if(strs==null||strs.length==0){
			return "";
		}
		String pre=strs[0];
		int count=strs.length;
		for (int i = 1; i < count; i++) {
			pre=longestCommonPrefix4(pre,strs[i]);
			if(pre.length()==0) {
				break;
			}
		}
		return pre;
    }
	//求两个字符串的最长公共前缀
	public String longestCommonPrefix4(String str1, String str2) {
		int len=Math.min(str1.length(),str2.length());
		int index=0;
		while (index<len&&str1.charAt(index)==str2.charAt(index)){
			index++;
		}
		return str1.substring(0,index);
	}
	//纵向
	public String longestCommonPrefix2(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		int length = strs[0].length();
		int count = strs.length;
		for (int i = 0; i < length; i++) {
			char c = strs[0].charAt(i);
			for (int j = 1; j < count; j++) {
				if (i == strs[j].length() || strs[j].charAt(i) != c) {
					return strs[0].substring(0, i);
				}
			}
		}
		return strs[0];
	}

	//分治
	public String longestCommonPrefix3(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		} else {
			return longestCommonPrefix3(strs, 0, strs.length - 1);
		}
	}

	public String longestCommonPrefix3(String[] strs, int start, int end) {
		if(start==end){
			return  strs[start];
		}else {
			int m=(end-start)/2+start;
			String l=longestCommonPrefix3(strs,start,m);
			String r=longestCommonPrefix3(strs,m+1,end);
			return commonPrefix(l,r);
		}
	}
	public  String commonPrefix(String l,String r){
		int m=Math.min(l.length(),r.length());
		for (int i = 0; i < m; i++) {
			if(l.charAt(i)!=r.charAt(i)){
				return l.substring(0,i);
			}
		}
		return l.substring(0,m);
	}

	//二分查找,取最短的一个字符串的长度为边界
	public String longestCommonPrefix(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		int minLength = Integer.MAX_VALUE;
		for (String str : strs) {
			minLength = Math.min(minLength, str.length());
		}
		int low = 0, high = minLength;
		while (low < high) {
			int mid = (high - low + 1) / 2 + low;
			if (isCommonPrefix(strs, mid)) {
				low = mid;
			} else {
				high = mid - 1;
			}
		}
		return strs[0].substring(0, low);
	}

	public boolean isCommonPrefix(String[] strs, int length) {
		String str0 = strs[0].substring(0, length);
		int count = strs.length;
		for (int i = 1; i < count; i++) {
			String str = strs[i];
			for (int j = 0; j < length; j++) {
				if (str0.charAt(j) != str.charAt(j)) {
					return false;
				}
			}
		}
		return true;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
